#include <bits/stdc++.h>
using namespace std;

/*
2999. 统计强大整数的数目
已解答
困难
相关标签
相关企业
提示
给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。

如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

 

示例 1：

输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。
示例 2：

输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。
示例 3：

输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。
 

提示：

1 <= start <= finish <= 1015
1 <= limit <= 9
1 <= s.length <= floor(log10(finish)) + 1
s 数位中每个数字都小于等于 limit 。
s 不包含任何前导 0 。
*/

// 法一
class Solution {
public:
    using ll = long long;  
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        // 计算[0, finish]范围内的合法数 - [0, start-1]范围内的合法数
        return cnt(finish, limit, s) - cnt(start - 1, limit, s);
    }

    // 计算[0, x]范围内符合以下条件的数字数量：
    // 1. 所有数位不超过limit 
    // 2. 以字符串s作为后缀
    ll cnt(ll x, int limit, string s) {
        string x_str = to_string(x);
        int x_len = x_str.size();
        int s_len = s.size();

        // 情况1：x的位数比s少，不可能包含s作为后缀
        if (x_len < s_len) return 0;  
        
        // 情况2：x的位数等于s的位数，直接比较是否大于等于s
        if (x_len == s_len) return (x_str >= s) ? 1 : 0;

        // 情况3：x的位数多于s的位数，处理前缀部分
        int pre_len = x_len - s_len;  // 前缀部分的位数
        ll ans = 0;
        string prefix = x_str.substr(0, pre_len);  // 分离前缀字符串

        // 逐位处理前缀部分，计算所有可能的前缀组合数
        for (int i = 0; i < pre_len; ++i) {
            int cur = prefix[i] - '0';  // 当前位的数值
            
            // 如果当前位超过limit，后续位可以任意填充符合条件的数字
            if (cur > limit) {
                // 计算剩余位数的全排列数：(limit+1)的剩余位数次方
                ans += pow_helper(limit + 1, pre_len - i);
                return ans;  // 后续位无法改变结果，直接返回
            } else {
                // 当前位可以取[0, cur-1]时的组合数，乘以剩余位的全排列数
                ans += (ll)cur * pow_helper(limit + 1, pre_len - i - 1);
            }
        }

        // 处理前缀完全等于x的前缀的情况，需要检查后缀是否合法
        string suffix = x_str.substr(pre_len);  // 分离后缀部分
        if (suffix >= s) {  // 后缀必须不小于s
            ans += 1;       // 如果满足条件，当前前缀对应的数字是合法的
        }
        return ans;
    }

    // 辅助函数：计算base^exp，用于计算全排列数
    ll pow_helper(int base, int exp) {
        if (exp < 0) return 0;  // 指数为负时无意义，返回0
        ll ans = 1;
        for (int i = 0; i < exp; ++i) {
            ans *= base;
        }
        return ans;
    }
};

// 法二
class Solution {
	public:
	// 计算[0, x_str]范围内符合以下条件的数字数目：
	// 1. 所有数位<=limit 
	// 2. 以字符串s结尾
	long long getNum(string x_str, string s, int limit) {
		// 当数字的位数比后缀长度更小时，直接不可能存在
		if (x_str.size() < s.size()) {
			return 0;
		}
		// 当位数相等时，直接比较整个数字是否>=s
		if (x_str.size() == s.size()) {
			return x_str >= s; // 利用字符串的字典序比较
		}

		// 前缀部分的长度（总长度减去后缀长度）
		int preLen = x_str.size() - s.size();
		long long cnt = 0;

		// 处理前缀部分的每一位
		for (int i = 0; i < preLen; ++i) {
			char current_digit = x_str[i];
			// 当前位的数值超过limit的情况
			if (current_digit > (limit + '0')) {
				// 赋予剩余位数的所有可能组合（例如limit=9时有10种可能）
				// 注意这里使用pow可能有精度丢失风险（例如大指数时）
				cnt += pow(limit + 1, preLen - i); // (limit+1)^(剩余位数)
				return cnt; // 直接返回，后续更大数值不会超过x_str的范围
			} else {
				// 计算当前位取[0, current_digit-1]时的组合数
				// 例如current_digit=3时，可以选0、1、2共三种情况
				cnt += (current_digit - '0') * pow(limit + 1, preLen - i - 1); // 乘剩余位数的可能性
			}
		}

		// 处理前缀部分相等的情况，检查后缀是否合法
		string suffix = x_str.substr(x_str.size() - s.size()); // 获取真实后缀
		cnt += (suffix >= s); // 后缀必须>=目标后缀
		
		return cnt;
	}

	// 主函数：计算区间[start, finish]中的强大数
	long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
		// 注意：当start=0时，start-1会得到负值，但此处逻辑仍然正确
		return getNum(to_string(finish), s, limit) - 
			   getNum(to_string(start - 1), s, limit);
	}
};